class Splay {
public:
    Splay() {}

    Splay(int n) {
        init(n);
    }

    void init(int n) {
        cnt = head = 0;
        Tree.assign(n + 5, {});
    }

    // add a num to the Tree
    void add(int num) {
        add(head, num);
    }

    // find the rank`s node in the Tree`s inorder
    int find(int rank) {
        return find(head, rank);
    }

    // query the num`s rank in the Tree
    int rank(int num) {
        return rank(head, num);
    }

    // return x-th`s value after sorting
    int index(int x) {
        int i = find(x);
        splay(i, 0);
        return Tree[i].key;
    }

    // return the pre num`s value
    int pre(int num) {
        return pre(head, num);
    }

    // return the post num`s value
    int post(int num) {
        return post(head, num);
    }

    // remove a num from the Tree
    void remove(int num) {
        int kth = rank(num);
        if(kth != rank(num + 1)) {
            int i = find(kth);
            splay(i, 0);
            if(Tree[i].ls == 0) {
                head = Tree[i].rs;
            } else if(Tree[i].rs == 0) {
                head = Tree[i].ls;
            } else {
                int j = find(kth + 1);
                splay(j, i);
                Tree[j].ls = Tree[i].ls;
                Tree[Tree[j].ls].father = j;
                up(j);
                head = j;
            }
            Tree[head].father = 0;
        }
    }

private:

    // Summary all the info about node[i]`s son
    void up(int i) {
        Tree[i].size = Tree[Tree[i].ls].size + Tree[Tree[i].rs].size + 1;
    }

    // check i is the right child of its father
    int lr(int i) {
        return Tree[Tree[i].father].rs == i ? 1 : 0;
    }

    void rotate(int i) {
        int f = Tree[i].father, g = Tree[f].father, soni = lr(i), sonf = lr(f);
        if(soni == 1) {
            Tree[f].rs = Tree[i].ls;
            if(Tree[f].rs != 0) {
                Tree[Tree[f].rs].father = f;
            }
            Tree[i].ls = f;
        } else {
            Tree[f].ls = Tree[i].rs;
            if(Tree[f].ls != 0) {
                Tree[Tree[f].ls].father = f;
            }
            Tree[i].rs = f;
        }
        if(g != 0) {
            if(sonf == 0) {
                Tree[g].ls = i;
            } else {
                Tree[g].rs = i;
            }
        }
        Tree[i].father = g;
        Tree[f].father = i;
        up(f);
        up(i);
    }

    // make node[i] is a child of node[goal]
    void splay(int i, int goal) {
        int f = Tree[i].father, g = Tree[f].father;
        while(f != goal) {
            if(g != goal) {
                if(lr(i) == lr(f)) {
                    rotate(f);
                } else {
                    rotate(i);
                }
            }
            rotate(i);
            f = Tree[i].father;
            g = Tree[f].father;
        }
        if(goal == 0) {
            head = i;
        }
    }

    void add(int i, int num) {
        Tree[++cnt].key = num;
        Tree[cnt].size = 1;
        if(head == 0) {
            head = cnt;
        } else {
            int f = 0, son = 0;
            while(i != 0) {
                f = i;
                if(Tree[i].key <= num) {
                    son = 1;
                    i = Tree[i].rs;
                } else {
                    son = 0;
                    i = Tree[i].ls;
                }
            }
            if(son == 0) {
                Tree[f].ls = cnt;
            } else {
                Tree[f].rs = cnt;
            }
            Tree[cnt].father = f;
            splay(cnt, 0);
        }
    }

    int find(int i, int rank) {
        while(i != 0) {
            if(Tree[Tree[i].ls].size + 1 == rank) {
                return i;
            } else if(Tree[Tree[i].ls].size >= rank) {
                i = Tree[i].ls;
            } else {
                rank -= Tree[Tree[i].ls].size + 1;
                i = Tree[i].rs;
            }
        }
        return 0;
    }

    int rank(int i, int num) {
        int ans = 0, f = 0;
        while(i != 0) {
            f = i;
            if(Tree[i].key >= num) {
                i = Tree[i].ls;
            } else {
                ans += Tree[Tree[i].ls].size + 1;
                i = Tree[i].rs;
            }
        }
        splay(f, 0);
        return ans + 1;
    }

    int pre(int i, int num) {
        int last = head;
        int ans = std::numeric_limits<int>::min();
        while(i != 0) {
            last = i;
            if(Tree[i].key < num) {
                ans = std::max(ans, Tree[i].key);
                i = Tree[i].rs;
            } else {
                i = Tree[i].ls;
            }
        }
        splay(last, 0);
        return ans;
    }

    int post(int i, int num) {
        int last = head;
        int ans = std::numeric_limits<int>::max();
        while(i != 0) {
            last = i;
            if(Tree[i].key > num) {
                ans = std::min(ans, Tree[i].key);
                i = Tree[i].ls;
            } else {
                i = Tree[i].rs;
            }
        }
        splay(last, 0);
        return ans;
    }

    struct Node {
        int ls, rs, size, father, key;
    };

    int cnt, head;
    std::vector<Node> Tree;
};